class Solution {

    private static final int mod =(int)1e9+7;
    char[] s;
    int[][] memo;

    public int countSteppingNumbers(String low, String high) {
       return (f(high)-f(low)+mod+(flag(low)?1:0))%mod;
    }

    public int f(String n)
    {
        this.s = n.toCharArray();
        int m = s.length;
        memo = new int[m][10];
        // for(int[] t:memo)
        // {
        //     Arrays.fill(t,-1);
        // }
          for (int i = 0; i < m; i++)
            Arrays.fill(memo[i], -1);
        return dfs(0,0,true,false);
    }
    public int dfs(int i,int pre,boolean is_limit,boolean is_num)
    {
        if(i==s.length)
        {
           return is_num?1:0;
        }
        if(!is_limit&&is_num&&memo[i][pre]!=-1)
        {
            return memo[i][pre];
        }
        int res = 0;
        if(!is_num)
        {
            res = dfs(i+1,pre,false,false);
        }
        int up = is_limit?s[i]-'0':9;
        for(int d = is_num?0:1;d<=up;d++)
        {
            if(!is_num||Math.abs(d-pre)==1)
            {
                res=(res+dfs(i+1,d,is_limit&&d==up,true))%mod;
            }
        }
        if(!is_limit&&is_num)
        {
            memo[i][pre] = res;
        }
        return res;
    }
    public boolean flag(String n)
    {
       for(int i = 1;i<n.length();i++)
       {
        if(Math.abs((int)n.charAt(i)-(int)n.charAt(i-1))!=1)
        {
            return false;
        }
       }
        return true;
    }
}